package SwordFingerOffer;

public class Q14_CutRope {
    //剪绳子 算乘积

    //一个小动态规划
    public static int cuttingRope(int n) {

        if (n < 4){
            return n == 0 || n == 1 ? 0 : n == 2 ? 1 : 2;
        }

        int[] dp =  new int[n + 1];
        //以下dp不是真实的答案 是为了服务我们的后续的dp计算
        //真实答案我们提前返回了

        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3 ;
        //F(5) = max(F(4) * 1，F(3) * 2...F(1) * 4)
        for (int i = 4; i <= n; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = 1; j <= i - 1 ; j ++) {
                max = Math.max(j * dp[i - j], max);
            }
            dp[i] = Math.max(dp[i - 1],max);
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(cuttingRope(10));
    }

}
